# !/usr/usuari/des python
#  -*- coding: utf-8 -*-
"""
@Author        : itgnay
@Time          : 2022/12/20 2:00
@FileName      : 回路计数.py
@LastEditors   : None
@Editors       : PyCharm
"""
"""
题目：
蓝桥学院由 21 栋教学楼组成，教学楼编号 1 到 21。对于两栋教学楼 a 和 b，当 a 和 b 互质时，a 和 b 之间有一条走廊直接相连，两个方向皆可通行，否则没有直接连接的走廊。
小蓝现在在第一栋教学楼，他想要访问每栋教学楼正好一次，最终回到第一栋教学楼（即走一条哈密尔顿回路），请问他有多少种不同的访问方案？
两个访问方案不同是指存在某个 i，小蓝在两个访问方法中访问完教学楼 i 后访问了不同的教学楼。
"""
import numpy as np

d = {}
for key in range(1, 22):
    value = []
    for v in range(1, 22):
        a, b = key, v
        while b > 0:
            a, b = b, a % b
        if a == 1:
            value.append(v)
    d[key] = value
dp = np.zeros((1 << 21, 21))  # dp[i][j]表示以第j楼为终点的状态i有多少种可能
dp[1][0] = 1
for i in range(1 << 21):
    for j in range(21):
        # 如果楼层j不存在，则不执行
        if (i >> j) % 2 == 0:
            continue
        # 遍历j可能到达的楼层
        for k in d[j + 1]:
            if (i >> (k - 1)) % 2 == 1:
                # 如果楼层k已经存在，不执行
                continue
            dp[i + (1 << (k - 1))][k - 1] += dp[i][j]
count = 0
for i in range(1, 21):
    count += int(dp[(1 << 21) - 1][i])
print(count)
